complexity A normal (deterministic) Turing Machine that

has a "guessing head" - a write-only head that writes a guess

at a solution on the tape first, based on some arbitrary

internal algorithm. The regular Turing Machine then runs

and returns "yes" or "no" to indicate whether the solution is

correct.